package com.example.leetdemo.process;

import java.util.*;

public class Solution15 {

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        int[] arr = new int[set.size()];
        int index = 0;
        for (Integer nu : set) {
            arr[index++] = nu;
        }
        Arrays.sort(arr);
        for (int i = 0; i < arr.length - 2; i++) {
            if (arr[i] >= 0) {
                break;
            }
            for (int j = i + 1; j < arr.length - 1; j++) {
                int other = -arr[i] - arr[j];
                if (other < 0) {
                    break;
                }
                if (set.contains(other) && arr[i] != other && arr[j] != other) {
                    List<Integer> list1 = new ArrayList<>();
                    list1.add(arr[i]);
                    list1.add(arr[j]);
                    list1.add(other);
                    list.add(list1);
                }
            }
        }
        return list;
    }

    public List<List<Integer>> threeSum1(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        int p = 0, q = n - 1;
        while (p < q - 1) {
            for (int i = p + 1; i < q; i++) {
                if (nums[p] + nums[i] + nums[q] == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[p]);
                    list.add(nums[i]);
                    list.add(nums[q]);
                    ans.add(list);
                    break;
                }
            }
            if (nums[q] + nums[p] < 0) {
                while (p + 1 < q && nums[p] == nums[p + 1]) {
                    p++;
                }
                p++;
            } else if (nums[q] + nums[p] > 0) {
                while (p < q - 1 && nums[q] == nums[q - 1]) {
                    q--;
                }
                q--;
            } else {
                while (p + 1 < q && nums[p] == nums[p + 1]) {
                    p++;
                }
                while (p < q - 1 && nums[q] == nums[q - 1]) {
                    q--;
                }
                p++; q--;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution15 solution15 = new Solution15();
        List<List<Integer>> list = solution15.threeSum1(new int[] {-2,0,1,1,2});
        System.err.println(list.size());
    }

}
